中国大学mooc视频地址 程序设计与算法（二）算法基础
直接看一道例题
例题一 数字三角形
（一）采用递归方法
思路：此题是标准的递归思维
首先想想第一步怎么走， 首先确定第一个是D[i][j]，那么下一步是D[i+1][j]或 D[i+1][j+1]
如此便形成相似的循环，可以用递归解决 那么边界条件是什么呢？当递归到最 后一行的时候就可以跳出 即if(i==n)为边界条件。
【将原问题拆为若干子问题，在这里原问题（D[i][j]到最后的最大和）的子问题就是D[i][j]的下一个D[i+1][j]或D[i+1][j+1]到最后的最大和】
·······总结下来就是
一个位置到最后的最大和 等于 这个位置的[i+1][j]和[i+1][j+1]中到最后的最大和的较大值 加上这个位置本身
（递归代码如下：
#include<iostream>
#include<algorithm>
#define MAX 101
using namespace std;
int D[MAX][MAX];
int n;
int MaxSum(int i, int j){
if(i==n)
return D[i][j]
else{
int x = MaxSum(i+1,j);
int y = MaxSum(i+1,j+1);
return max(x,y)+D[i][j];
}
int main()
{
int i,j;
cin >> n;
for(i = 1; i <= n; i++)
for(j = 1; j <= i; j++)
cin >> D[i][j];
cout << MaxSum(1,1) <<endl;
return 0;
}
（二）采用记忆递归型动归
解决这种重复计算的方法即记下之前算过的从而避免重复：
数字三角形的记忆递归型动归程序：
动归代码如下：
#include<iostream>
#include<algorithm>
#define MAX 101
using namespace std;
int D[MAX][MAX];
int maxSum[MAX][MAX]; //存放算过的值
int n;
int MaxSum(int i, int j){
if(maxSum[i][j] != -1) //判断是否算过了
return maxSum[i][j];
if(i==n)
maxSum[i][j] = D[i][j];
else{
int x = MaxSum(i+1,j);
int y = MaxSum(i+1,j+1);
maxSum[i][j] = max(x,y) + D[i][j];
}
return maxSum[i][j]; //整体return了 这点仔细想想
int main()
{
int i,j;
cin >> n;
for(i = 1; i <= n; i++)
for(j = 1; j <= i; j++){
cin >> D[i][j];
maxSum[i][j] = -1;
}
cout << MaxSum(1,1) <<endl;
return 0;
}
（三）将递归进阶成递推
重新分析，可以从最后一行开始，一行行往上递推
#include<iostream>
#define MAX 101
using namespace std;
int main()
{
int D[MAX][MAX];
int maxSum[MAX][MAX];
int n,i,j;
cin >> n;
for(i = 1; i <= n; i++)
for(j = 1;j <=i; j++)
cin >> D[i][j];
for(i = 1; i <=n; i++) //对边界条件进行初始化
maxSum[n][i] = D[n][i]; //最后一行的结果就是它本身
for(i = n-1; i>=1; i--) //从倒是第二行开始往上递推，
for(j = 1; j <=i; j++)
maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j];
cout << maxSum[1][1] <<endl;
return 0;
}
（四）递推的空间优化 —滚动数组（存疑）
在三的递推中，发现其实并不需要一个maxSum[i][j]来记录结果，可以用一个maxSum[i]一维数组来记录，新纪录的可以将旧的结果覆盖，因为不要再用它了，然后再想想 发现其实可以用一个*maxSum 也可以实现
#include<iostream>
#define MAX 101
using namespace std;
int main()
{
int D[MAX][MAX];
int *maxSum;
int n,i,j;
cin >> n;
for(i = 1; i <= n; i++)
for(j = 1;j <=i; j++)
cin >> D[i][j];
maxSum = D[n];
for(i = n-1; i>=1; i--)
for(j = 1; j <=i; j++)
maxSum[j] = max(maxSum[j],maxSum[j+1])+D[i][j];
cout << maxSum[1] <<endl;
return 0;
}
（五）总结：从递归到递推/动规
- **··递归到递推的一般转化方法：
1.递归函数有n个参数，就定义一个n维的数组 2.数组的下标是递归函数参数的取值范围 3.数组元素的值是递归函数的返回值 4.从边界值出发，逐步填充数组，相当于计算递归函数值的逆过程**
- **··动规解题的一般思路：
1.将原问题拆分成若干小问题（类似于递归的思路），但与递归不同的是要将每次计算的结果存下来，避免重复计算。 【可参照上面数字三角形的例子】 2.确定状态 一个状态就是一个子问题，上述例子有多少数字就有多少状态 3.确定一些初始状态（边界状态）的值 4.确定状态转移方程 如何从一个或多个已知值的状态 求出另一个状态的值 可以用递推式表示，即状态转移方程。 如数字三角形中的状态转移方程**
··能用动规解决的问题的特点：
1.问题具有最优子结构性质。
指问题的最优解所包含的子问题的解也是最优的
2.无后效性
当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态值有关，和之前是采取哪种手段或哪条路径演变到当前的这若干个状态没关